package newcoder_exp.justPractise;

import java.util.*;
import org.junit.*;

public class NC158 {
    public class Solution1 {
        public int findShortestPath(int n, int m, int[][] graph) {
            int[] minPath = new int[m + 1];
            Set<Integer> visited = new HashSet<>();
            int curPath = 0;
            minPath[1] = 0;
            for (int i = 2; i <= m; i++) {
                minPath[i] = Integer.MAX_VALUE;
            }
            visited.add(1);// 1已经遍历过
            int next;
            for (int i = 1; i <= m; i++) {
                next = getNearest(graph[i], visited);
            }
            return minPath[n];
        }

        public void fresh(int[] minPath, int curPath, int edge) {

        }

        public int getNearest(int[] g, Set<Integer> visited) {
            int min = 0;
            for (int i = 1; i < g.length; i++) {
                if (visited.contains(i) && g[i] < g[min]) {
                    i = min;
                }
            }
            return min;
        }
    }

    /* 
    
    [[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]

    ‘*/
    public class Solution {
        //graph[i] 是一个三元组，表示 from to weight
        public int findShortestPath(int n, int m, int[][] graph) {
            int[][] dp = new int[n][n];
            for (int[] d : dp) { 
                Arrays.fill(d, Integer.MAX_VALUE);
            } //初始化：所有节点的最短路径都为无穷
            for (int[] edge : graph) {
                //重复边 要拿老的dp[i][j]做比较 （重复边是指：三元组[i,j,k1]与[i,j,k2], 因此i,j最短路径需要k1,K2较小者)
                dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2], dp[edge[0] - 1][edge[1] - 1]);
            }
            // 优先队列按照花费进行从小到大的排序
            PriorityQueue<CityInfo> queue = new PriorityQueue<CityInfo>((o1, o2) -> {
                return o1.cost - o2.cost;
            });
            queue.offer(new CityInfo(0, 0));
            while (!queue.isEmpty()) {
                CityInfo info = queue.poll();
                // 如果到达了终点，而queue.poll的就是花费最低的，那么就给其返回
                if (info.dst == n - 1) {//djstra思想，每一步都通过小顶堆取最短路径的顶点最终到达n也是最短的
                    return info.cost;
                }
                // 到达目前的该点到其他点的路线是否存在，如果存在，就加入到队列中
                for (int i = 0; i < n; i++) {
                    if (dp[info.dst][i] != Integer.MAX_VALUE) { //查找当前节点的邻接边
                        queue.offer(new CityInfo(i, dp[info.dst][i] + info.cost)); //info.cost,即从起点到当前info这个点的最短路径，dp[info,dst][i],表示info点到达下一个邻接点的距离
                    }
                }
            }
            return -1;
        }

        class CityInfo {
            int dst; //目的地编号(从0~m-1, 少一个)
            int cost; //最短路径长度

            public CityInfo(int dst, int cost) {
                this.dst = dst;
                this.cost = cost;
            }
        }
    }

}
